
#include "alloc_context_impl.h"
#include "alloc.h"
#include "helpers.h"

#include <stdlib.h>
#include <string.h>

/*
 * l and r - shall be pointers to pointers to Id
 */
static int
ids_comparison( const void * l, const void * r )
{
    const Id *  lhs = *(const Id **)l;
    const Id *  rhs = *(const Id **)r;

    return idcmp( lhs, rhs );
}


static char *
alloc_string(
    AllocContext *  c,
    size_t          str_size
    )
{
    char *          result;
    LitArr *        la;

    // string is too big to fit within the buffer
    if( str_size >= c->settings.literals_arr_grow_size )
    {
        alloc_emit_error( c, QL_ERR_WRONG_CONF );
    }

    // may be string can fit in any of the previously allocated buffers
    for( la = c->impl->ids.lit_arr; la != 0; la = la->next )
    {
        size_t      new_size = la->size + str_size + 1;
        if( new_size < c->settings.literals_arr_grow_size )
        {
            result = la->buffer + la->size;
            la->size = new_size;
            return result;
        }
    }

    // array was not allocated yet or string is too big to fit within current storages
    la = ql_mallocz( c,
        c->settings.literals_arr_grow_size * sizeof(char) + sizeof(LitArr) - 1 );

    if( 0 != c->impl->ids.lit_arr )
    {
        LitArr * full_la = c->impl->ids.lit_arr;
        la->next = full_la;
    }

    c->impl->ids.lit_arr = la;

    result = la->buffer + la->size;
    la->size = la->size + str_size + 1;

    return result;
}

/*
 * finds allocated string
 * @param   c
 * @param   hash
 * @param   elem_namespace
 * @param   found_id        output identifier who matches with the hash/namespace provided
 * @param   found_str       output string which matches with the hash provided
 */
static void search_id(
    AllocContext *  c,
    StrHash         hash,
    Id *            elem_namespace,
    Id **           found_id,
    const char **   found_str
    )
{
    SortedIdsArr *  si = &c->impl->ids.sorted_ids;
    size_t          lower = 0;
    size_t          upper = si->size;
    Id              key;

    key.hash = hash;
    key.ns = elem_namespace;

    if( upper == 0 )
        return;

    // performs binary search
    // this replaces bsearch for efficiency, since we need to perform 2 searches in 1
    while( lower < upper )
    {
        size_t      index = (lower + upper) / 2;
        Id *        current = si->arr[index];
        int         diff = key.hash - current->hash;

        // string has been found?
        if( 0 == diff )
        {
            diff = cmp_ids_namespaces( &key, current );

            // if namespaces matches too, then the exact match is found
            if( 0 == diff )
            {
                *found_id = current;
                return;
            }

            // string is found - no need to allocate another one
            *found_str = current->str;
        }

        if( diff < 0 )
        {
            upper = index;
        }
        else
        {
            lower = index + 1;
        }
    }
}

// allocators
Id * alloc_id_len(
    AllocContext *  c,
    const char *    id_str,
    size_t          id_len,
    Id *            elem_namespace
    )
{
    SortedIdsArr *  si = &c->impl->ids.sorted_ids;
    StrHash         hash = hash_from_str( id_str, id_len );

    const char *    alloc_str = 0;
    Id *            r = 0;

    // find whether the same identifier was allocated
    // or at least whether the same string was allocated
    search_id( c, hash, elem_namespace, &r, &alloc_str );

    // if there are no such an identifier - allocate new place for that
    if( 0 == r )
    {
        IdArr *     ia = c->impl->ids.id_arr;

        // if this string is not present yet - allocate place for that
        if( 0 == alloc_str )
        {
            // allocate place for identifier string & copy source string there
            char * new_str = alloc_string( c, id_len );
            memcpy( new_str, id_str, id_len );
            new_str[id_len] = 0;
            
            alloc_str = new_str;
        }

        // allocate more space for identifiers array if it is needed
        if( (0 == ia) ||
            ((ia->size + 1) >= c->settings.id_arr_grow_size) )
        {
            IdArr * prev_ia = ia;
            ia = ql_mallocz( c, (c->settings.id_arr_grow_size - 1) * sizeof(Id) + sizeof(IdArr) );

            c->impl->ids.id_arr = ia;
            ia->next = prev_ia;
        }

        // allocate place for new one identifier
        r = &ia->arr[ia->size ++];

        // fill identifier's contents
        r->hash = hash;
        r->str = alloc_str;
        r->ns = elem_namespace;
        r->type = OBJ_ID;

        // allocate place for new symbol within the lookup table
        if( (si->size + 1) >= si->allocated )
        {
            size_t  new_alloc = si->allocated + c->settings.id_arr_grow_size;
            Id ** new_arr = ql_realloc( c, si->arr, new_alloc * sizeof(Id *) );

            si->arr = new_arr;
            si->allocated = new_alloc;
        }

        si->arr[si->size ++] = r;

        // sort identifiers array in order to use binary search next time
        qsort( si->arr, si->size, sizeof(Id *), ids_comparison );
    }

    return r;
}

Id * alloc_id(
    AllocContext *  c,
    const char *    id_str,
    Id *            elem_namespace
    )
{
    return alloc_id_len( c, id_str, strlen(id_str), elem_namespace );
}

void free_ids_buffers( AllocContext * c )
{
    IdArr *         ia = c->impl->ids.id_arr;
    LitArr *        la = c->impl->ids.lit_arr;

    // free each literals buffer
    for( ; la != 0; )
    {
        LitArr *    next_la = la->next;
        ql_free( la );
        la = next_la;
    }

    // free lookup table
    if( c->impl->ids.sorted_ids.arr )
    {
        ql_free( c->impl->ids.sorted_ids.arr );
    }

    // free identifiers buffer
    for( ; ia != 0; )
    {
        IdArr *  next_ia = ia->next;
        ql_free( ia );
        ia = next_ia;
    }
}
